So let's conclude all of this. The idea is we have two ways to improve a classical search

algorithm on constraint networks, namely either we do inference, whereby inference we go over

to a network which is equivalent and tighter. Forward checking is the simplest case. Improvements

over forward checking using R consistency and then you get these algorithms AC1 or AC3.

The other thing you can do is to try to decompose your network into several networks and solve

them individually. The obvious way to do that is if you have networks that have disconnected

components so you can solve those separately and then you can use cut-set conditioning

to abuse the fact that certain sub-graphs of your constraint graph happen to be acyclic.

There's also a lot of things we didn't cover here. If you're interested in them you may

be interested in Googling all of this or looking it up on Wikipedia or of course in Russell

and Norwick. Most of them are probably treated in there at least superficially so you get

an idea of what it's all about. Then tomorrow we'll go over to talk about knowledge and

inference in general.